

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Solution429 {
    class Node {
        public int val;
        public List<Node> children;

        public Node() {}

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, List<Node> _children) {
            val = _val;
            children = _children;
        }
    };

    class NodeInfo{
        public Node node;
        public int level;

        NodeInfo(Node node, int level){
            this.node = node;
            this.level = level;
        }
    }

    private void addToRes(List<List<Integer>> res, int level, int val){
        while(res.size() <= level){
            res.add(new ArrayList<>());
        }
        res.get(level).add(val);
    }

    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> res = new ArrayList<>();
        if(root == null){ return res; }
        Queue<NodeInfo> q = new LinkedList<>();
        q.add(new NodeInfo(root, 0));
        while(!q.isEmpty()){
            NodeInfo nodeInfo = q.poll();
            Node tmpNode = nodeInfo.node;
            int tmpLevel = nodeInfo.level;
            addToRes(res, tmpLevel, tmpNode.val);
            int nextLevel = tmpLevel + 1;
            List<Node> children = tmpNode.children;
            for(Node child : children){
                q.add(new NodeInfo(child, nextLevel));
            }
        }
        return res;
    }
}
